package com.itzmn.examinations.shumeikeji;

import java.util.ArrayList;

/**
 * @Author: 张梦楠
 * @Date: 2019/1/16 21:19
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 数美科技面试题
 *
 *   给定一个集合，内部装着集合，将所有集合中数据排序，返回一个集合
 *   思路：使用了归并排序
 */
public class Class3 {

    public static void main(String[] args) {

        new Class3().init();
    }

    private void init() {

        ArrayList<Integer> integers = new ArrayList<>();
        ArrayList<Integer> integers1 = new ArrayList<>();

        integers.add(2);
        integers.add(3);
        integers1.add(6);
        integers.add(5);
        integers1.add(7);
        integers1.add(8);
        integers.add(9);
        ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
        arrayLists.add(integers);
        arrayLists.add(integers1);
        ArrayList<Integer> sort = sort(arrayLists, 0, 1);
        for (Integer i:sort){
            System.out.print(i+" ");
        }
    }
    ArrayList<Integer> merge(ArrayList<ArrayList<Integer>> seqs) {
        ArrayList<Integer> sort = sort(seqs, 0, seqs.size() - 1);
        return sort;
    }

    public ArrayList<Integer> sort(ArrayList<ArrayList<Integer>> lists,int L,int R){

        if (L == R){
            return lists.get(L);
        }
        int mid = (L + R) /2 ;
        ArrayList<Integer> sort = sort( lists, L, mid);
        ArrayList<Integer> sort1 = sort( lists, mid + 1, R);
        ArrayList<Integer> me = me(sort, sort1);
        return me;
    }

    private ArrayList<Integer> me(ArrayList<Integer> integers1, ArrayList<Integer> integers2) {

        ArrayList<Integer> integers = new ArrayList<>();
        int l =0,a=0;
        while (l<integers1.size() && a<integers2.size()){
            integers.add(integers1.get(l) < integers2.get(a) ? integers1.get(l++) : integers2.get(a++));
        }

        while (l < integers1.size()){
            integers.add(integers1.get(l++));
        }
        while (a < integers2.size()){
            integers.add(integers2.get(a++));
        }
        return integers;
    }

}
